package algorithms.question.class22;

import common.util.MyUtil;

/**
 * https://leetcode-cn.com/problems/trapping-rain-water/
 *
 * @author guichang
 * @date 2021/8/27
 */

@SuppressWarnings("all")
public class Code2_接雨水 {

    public static void main(String[] args) {
        int[] nums = MyUtil.createArray(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1);
        MyUtil.print(trap(nums));
    }

    public static int trap(int[] nums) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        int N = nums.length;
        int maxL = nums[0]; // 0~l-1的最大值
        int maxR = nums[N - 1]; // r-1~N-1的最大值
        int l = 1, r = N - 2; // 左右俩指针
        int res = 0; // 收集的雨水
        while (l <= r) {
            // 结算左边
            if (maxL < maxR) {
                res += Math.max(0, maxL - nums[l]);
                maxL = Math.max(maxL, nums[l++]);
            }
            // 结算右边
            else {
                res += Math.max(0, maxR - nums[r]);
                maxR = Math.max(maxR, nums[r--]);
            }
        }
        return res;
    }

}